Implementing the Merge Sort Algorithm with Python
Merge sort is based on the divide and conquer algorithm, with three core steps: divide (split the array into left and right subarrays until single elements), recursively sort (recursively sort each subarray), and merge (merge the ordered subarrays into a single ordered array). Taking the array [3, 1, 4, 2] as an example, after decomposition, each subarray is recursively sorted and then merged into [1, 2, 3, 4]. The Python implementation includes a merge function (to merge two ordered subarrays in sequence) and a recursive sorting function (to decompose and recursively call merge). Its characteristics: time complexity O(n log n), space complexity O(n) (requires additional storage for merge results), and it is a stable sort (the relative order of equal elements remains unchanged).
Read MoreImplementing Heap Sort Algorithm with Python
Heap Sort is an efficient sorting algorithm that leverages the heap data structure, with a stable time complexity of O(n log n) and a space complexity of O(1), making it suitable for sorting large-scale data. A heap is a complete binary tree where parent node values are either greater than or equal to (max heap) or less than or equal to (min heap) their child node values. In an array representation, the indices of a heap follow these relationships: the children of a parent node at index i are located at 2i+1 and 2i+2, while the parent of a child node at index j is at (j-1)//2. The core operations include: 1. **Heapify**: Adjust the subtree rooted at index i to be a max heap by recursively comparing child nodes and swapping values as needed. 2. **Build Max Heap**: Starting from the last non-leaf node (n//2 - 1) and moving upward, adjust all nodes to ensure the entire tree satisfies the max heap property. The sorting process involves: first building the max heap, then repeatedly swapping the root (maximum value) with the last element of the heap, followed by calling Heapify to re-adjust the remaining elements into a max heap. This results in a sorted array from smallest to largest. Heap Sort is an in-place sorting algorithm, making it well-suited for scenarios with large data volumes.
Read More